1. Field of the Invention
The present invention relates to the field of data transmission, and in particular to a method and apparatus for analyzing the flow of data through one or more buffers.
2. Background Art
In electronic systems, data items are transmitted between data producers and data receivers. A first-in-first-out (FIFO) buffer is commonly used between such producers and receivers. It is desirable to ensure that the FIFO buffer does not become full (congested) or empty (starved) during the transmission. Thus, the state of the FIFO is monitored, which enables the data producer and data receiver to modify their transfer rates to avoid filling or emptying the queue. Prior art monitoring schemes are undesirable for use with ripple FIFO buffers. A ripple FIFO buffer is comprised of a plurality of FIFO buffers connected in series. This problem can be better understood by a review of data transmission.
Data Transmission
When data is transmitted from a data producer to a data receiver, problems arise when the data producer""s clock speed is different from the data receiver""s clock speed. The clock speed regulates how fast the device can execute commands. If the data producer""s clock speed is faster than the data receiver""s clock speed, the data receiver may be unable to process the data as quickly as it is sent. Thus, some data items in the transmission may be lost.
Buffers
A buffer is a space in a computer""s memory where data is temporarily stored. One use of a buffer is to prevent data loss due to differing clock speeds of separate computers attempting to exchange data. The data producer sends data items to the buffer. The buffer stores the data items until the data receiver is ready to receive more of the transmission. The buffer""s clock speed is typically at least as fast as the clock speeds of both the data producer and the data receiver. Thus, no data is lost as a result of differing clock cycles.
Additionally, data transmissions typically occur in bursts. Without buffers, the data producer and data receiver must devote some or all of their resources to handling the data transmissions as they happen. As a result, the data producer and data receiver experience gaps of time where resources are available to handle data transmission, but no transmission exists. Additionally, the data producer and data receiver experience times where resources are not available to handle data transmission, but a transmission must occur. Buffers allow the data producer and the data receiver to schedule the transmission to take advantage of the times when resources are available.
FIG. 1 illustrates the operation of a buffer for a data transmission. At step 100, it is determined whether the data producer sent a data item. If the data producer sent a data item, at step 110, the item is stored in the buffer and the process moves on to step 120. If the data producer did not send a data item, the process moves directly to step 120. At step 120, it is determined whether the data receiver requested a data item. If the data receiver requested a data item, at step 130, the buffer sends a data item to the data receiver and the process repeats at step 100. If the data receiver did not request a data item, the process repeats at step 100.
FIFO Buffers
First-in-first-out (FIFO) buffers ensure the data items are received by the data receiver in the same order they are sent by the data producer. A FIFO buffer always sends the oldest data item in the buffer to the data receiver first.
FIG. 2 illustrates the operation of a FIFO buffer. At step 200, it is determined whether the data producer sent a data item. If the data producer sent a data item, at step 210, the item is stored in the FIFO buffer and the process moves on to step 220. If the data producer did not send a data item, the process moves directly to step 220. At step 220, it is determined whether the data receiver requested a data item. If the data receiver did not request a data item, the process repeats at step 200. If the data receiver requested a data item, at step 230, the FIFO buffer locates the oldest data item in the FIFO buffer. At step 240, the FIFO buffer sends the oldest data item to the data receiver and the process repeats at step 200.
Ring FIFO Buffers
Conventional FIFO buffers are typically implemented using a ring buffer. A ring buffer has an amount of storage space, a read pointer and a write pointer. A pointer is a location in a computer""s memory that contains another memory location where data can be obtained or stored. As data items are added to the buffer, the write pointer is incremented to the next open position corresponding to the location in the computer""s memory where the next data item in the buffer will be stored. Similarly, as data items are sent to the data receiver, the read pointer is incremented. Once a pointer reaches the end of the buffer, it repeats at the beginning of the buffer.
FIG. 3 illustrates a ring FIFO buffer. Data Items A(300), B(310) and C(320) are stored in the buffer in locations 1 (330), 2 (340) and 3 (350) respectively. The write pointer (360) points at location 4 (370). The read pointer (380) points at location 1. Locations 4 and 5 (390) are empty.
Ripple FIFO Buffers
A ripple FIFO buffer is comprised of a plurality of FIFO buffers connected in series. FIG. 4 illustrates a ripple FIFO buffer. The ripple FIFO buffer (400) is comprised sub-buffers 1 (410), 2 (420) and 3 (430). A data item (440) sent by the data producer (450) to the data receiver (460) would first pass through sub-buffer 1. Then, the data item would pass through sub-buffer 2. Next, the data item would pass through sub-buffer 3 before being sent to the data receiver.
If the data transfers between sub-buffers are not regulated by a clock, the buffer is termed an xe2x80x9casynchronous ripple FIFO buffer.xe2x80x9d Ripple FIFO sub-buffers implemented with asynchronous building blocks are very fast relative to clock cycles of typical data producers and data receivers. Thus, asynchronous ripple FIFO buffers can be embedded in clocked systems. The clock signal of the data producer or data receiver can be used to generate a request to the asynchronous ripple FIFO buffer.
To allow maximum flexibility to deal with bursts at the data sender or data receiver, it is desirable that the FIFO buffer be kept neither completely full nor completely empty. Half full may be a desirable state, where the is sufficient room to store a data sender burst and sufficient data stored to satisfy a data receiver burst. In one method, if the FIFO buffer is greater than half full, the FIFO buffer is becoming congested. If the FIFO buffer is less than half full, the FIFO buffer is becoming starved.
In another method, some point other than half full is the boundary between becoming congested and becoming starved in a FIFO buffer. In yet another method, a range of fullness is defined as the boundary. For example, a FIFO buffer may only be considered becoming starved when it is less than one third full while it is only considered becoming congested when it is greater than two thirds full. An important concern is to avoid overflow or underflow.
It is important to ensure there is space available at the input end of the asynchronous ripple FIFO buffer whenever the data producer wishes to insert a data item. The situation where no space is available when the data producer attempts to insert a data item is termed xe2x80x9coverflow.xe2x80x9d
Additionally, it is important to ensure there is always a data item available at the output end of the asynchronous ripple FIFO buffer whenever the data receiver wishes to receive a data item. The situation where no data item is available when the data receiver attempts to remove a data item is termed xe2x80x9cunderflow.xe2x80x9d
Flow Control
In a conventional system, each end of a FIFO buffer operates in a different local clock domain. In some designs the two clocks are mesochronous. Mesochronous clocks have the same frequency but an unknown phase relationship. If the two clocks are mesochronous, the buffer should neither completely fill nor completely empty during data transmission.
In cases when the sender and receiver clocks are not mesochronous, or where communication is bursty, it is necessary to implement some sort of flow control to avoid completely filling or completely emptying the FIFO buffer. One prior art scheme for flow control is accomplished by monitoring the fullness, or relative occupancy, of the FIFO buffer and communicating this information to the data producer and data receiver to allow them to adjust their transfer rates.
FIG. 5 illustrates the operation of one embodiment of a flow controller. At step 500, it is determined whether the fullness of the buffer is above an upper threshold. If the fullness is not above an upper threshold, the process moves to step 530. If the fullness is above an upper threshold, at step 510, the buffer signals the data producer to decrease its transfer rate. At step 520, the buffer signals the data receiver to increase its transfer rate and the process moves to step 530. At step 530, it is determined whether the fullness of the buffer is below a lower threshold. If the fullness is not below a lower threshold, the process moves to step 500. If the fullness is below a lower threshold, at step 540, the buffer signals the data receiver to decrease its transfer rate. At step 550, the buffer signals the data producer to increase its transfer rate and the process moves to step 500.
Flow Control With Ripple FIFO Buffers
There are some disadvantages to using fullness to control flow with a ripple FIFO buffers. Individual ripple FIFO buffer sub-buffers rapidly alternate between full and empty states as data items move. The rapid alternation between full and empty states makes it difficult to estimate occupancy. Keeping a total of items in the buffer by monitoring the number of items inserted compared to the number of items removed is also difficult due to the decoupled nature of the interfaces with the data producer and the data receiver.
Additionally, fullness of the ripple FIFO buffer may not be the most useful measure for flow control. In the presence of congestion near the input of the ripple FIFO buffer, it is possible for input space to be unavailable even though the ripple FIFO buffer is nearly empty. Similarly, it is possible for the last sub-buffer to be empty even with the ripple FIFO buffer nearly full. If the ripple FIFO buffer is used to process the data in addition to buffering it, similar situations could arise due to data-dependent computation delays.
The present invention provides a method and apparatus for data flow control. One embodiment detects input congestion and output starvation in a plurality of sub-buffers of a ripple FIFO buffer. This embodiment is used to draw conclusions about the occupancy of the ripple FIFO buffer under steady-state conditions.
One embodiment detects input congestion and output starvation at every sub-buffer of the ripple FIFO buffer. Other embodiments detect input congestion and output starvation at a subset of the sub-buffers of the ripple FIFO buffer.
One embodiment determines occupancy of the ripple FIFO buffer by the number of sub-buffers which report a steady congested state. Another embodiment determines occupancy of the ripple FIFO buffer by the number of sub-buffers which report a steady starved state. Another embodiment determines occupancy of the ripple FIFO buffer by the location of sub-buffers which report a steady congested state. Another embodiment determines occupancy of the ripple FIFO buffer by the location of sub-buffers which report a steady starved state. Other embodiments determine occupancy of the ripple FIFO buffer by a combination of the above methods.